/*
 * Copyright (C) 2008-12  Bernhard Hobiger
 *
 * This file is part of HoDoKu.
 *
 * HoDoKu is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HoDoKu is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HoDoKu. If not, see <http://www.gnu.org/licenses/>.
 */
package sudoku;

import solver.SudokuSolver;

import javax.swing.*;
import java.awt.*;
import java.util.ArrayList;
import java.util.List;
import java.util.ResourceBundle;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author hobiwan
 */
@SuppressWarnings("serial")
public class BackdoorSearchDialog extends javax.swing.JDialog implements Runnable {

    private static final int MAX_FOUND = 100;
    private static final long serialVersionUID = 1L;
    private DefaultListModel singlesListModel;
    private DefaultListModel progressListModel;
    private SudokuPanel sudokuPanel;
    private Sudoku2 sudoku;
    private Sudoku2 orgSudoku;
//    private Sudoku2 solvedSudoku;
    private SudokuSolver solver;
    private List<Candidate> candidates = new ArrayList<Candidate>();
    private BlockingQueue<String> singlesQueue = new ArrayBlockingQueue<String>(20);
    private BlockingQueue<String> progressQueue = new ArrayBlockingQueue<String>(20);
    private Thread thread;
    private volatile int anzFound;
    private Runnable updateRunnable = new Runnable() {

        @Override
        public void run() {
            update();
        }
    };
    private Runnable progressBarRunnable = new Runnable() {

        @Override
        public void run() {
            updateProgressBar();
        }
    };
    // the following attributes maynot be used directly, only via their
    // synchronized getters and setters
    private boolean finished = false;
    private String progressLabelString = "";
    private int progressBarMax = 100;
    private int progressBarAct = 0;

    /** Creates new form BackdoorSearchDialog
     * @param parent
     * @param modal
     * @param sudokuPanel  
     */
    @SuppressWarnings("unchecked")
    public BackdoorSearchDialog(java.awt.Frame parent, boolean modal, SudokuPanel sudokuPanel) {
        super(parent, modal);
        initComponents();

        this.sudokuPanel = sudokuPanel;

        getRootPane().setDefaultButton(startButton);

        singlesListModel = new DefaultListModel();
        singlesResultList.setModel(singlesListModel);
        progressListModel = new DefaultListModel();
        progressResultList.setModel(progressListModel);

        if (Options.getInstance().getBdsSearchCandidatesAnz() < 0) {
            Options.getInstance().setBdsSearchCandidatesAnz(0);
        }
        cellsCheckBox.setSelected(Options.getInstance().isBdsSearchForCells());
        candidatesCheckBox.setSelected(Options.getInstance().isBdsSearchForCandidates());
        candComboBox.setSelectedIndex(Options.getInstance().getBdsSearchCandidatesAnz());
        candComboBox.setEnabled(candidatesCheckBox.isSelected());

    }

    /** This method is called from within the constructor to
     * initialize the form.
     * WARNING: Do NOT modify this code. The content of this method is
     * always regenerated by the Form Editor.
     */
    @SuppressWarnings("unchecked")
    // <editor-fold defaultstate="collapsed" desc="Generated Code">//GEN-BEGIN:initComponents
    private void initComponents() {

        configPanel = new javax.swing.JPanel();
        cellsCheckBox = new javax.swing.JCheckBox();
        candidatesCheckBox = new javax.swing.JCheckBox();
        candLabel = new javax.swing.JLabel();
        candComboBox = new javax.swing.JComboBox();
        progressPanel = new javax.swing.JPanel();
        searchLabel = new javax.swing.JLabel();
        searchProgressBar = new javax.swing.JProgressBar();
        resultPanel = new javax.swing.JPanel();
        singlesResultPanel = new javax.swing.JPanel();
        singlesResultLabel = new javax.swing.JLabel();
        jScrollPane1 = new javax.swing.JScrollPane();
        singlesResultList = new javax.swing.JList();
        progressResultPanel = new javax.swing.JPanel();
        progressResultLabel = new javax.swing.JLabel();
        jScrollPane2 = new javax.swing.JScrollPane();
        progressResultList = new javax.swing.JList();
        startButton = new javax.swing.JButton();
        closeButton = new javax.swing.JButton();
        stopButton = new javax.swing.JButton();

        setDefaultCloseOperation(javax.swing.WindowConstants.DISPOSE_ON_CLOSE);
        ResourceBundle bundle = ResourceBundle.getBundle("intl/BackdoorSearchDialog"); // NOI18N
        setTitle(bundle.getString("BackdoorSearchDialog.title")); // NOI18N

        configPanel.setBorder(javax.swing.BorderFactory.createTitledBorder(bundle.getString("BackDoorSearchDialog.configPanel.title"))); // NOI18N

        cellsCheckBox.setMnemonic(ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchPanel.cellsCheckBox.mnemonic").charAt(0));
        cellsCheckBox.setSelected(true);
        cellsCheckBox.setText(bundle.getString("BackdoorSearchPanel.cellsCheckBox.text")); // NOI18N
        cellsCheckBox.setToolTipText(bundle.getString("BackdoorSearchDialog.cellsCheckBox.toolTipText")); // NOI18N
        cellsCheckBox.addActionListener(new java.awt.event.ActionListener() {
            public void actionPerformed(java.awt.event.ActionEvent evt) {
                cellsCheckBoxActionPerformed(evt);
            }
        });

        candidatesCheckBox.setMnemonic(ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchPanel.candidatesCheckBox.mnemonic").charAt(0));
        candidatesCheckBox.setText(bundle.getString("BackdoorSearchPanel.candidatesCheckBox.text")); // NOI18N
        candidatesCheckBox.setToolTipText(bundle.getString("BackdoorSearchDialog.candidatesCheckBox.toolTipText")); // NOI18N
        candidatesCheckBox.addActionListener(new java.awt.event.ActionListener() {
            public void actionPerformed(java.awt.event.ActionEvent evt) {
                candidatesCheckBoxActionPerformed(evt);
            }
        });

        candLabel.setDisplayedMnemonic(ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchPanel.candLabel.mnemonic").charAt(0));
        candLabel.setLabelFor(candComboBox);
        candLabel.setText(bundle.getString("BackdoorSearchPanel.candLabel.text")); // NOI18N

        candComboBox.setModel(new javax.swing.DefaultComboBoxModel(new String[] { "1", "2", "3" }));
        candComboBox.setSelectedIndex(1);
        candComboBox.addActionListener(new java.awt.event.ActionListener() {
            public void actionPerformed(java.awt.event.ActionEvent evt) {
                candComboBoxActionPerformed(evt);
            }
        });

        javax.swing.GroupLayout configPanelLayout = new javax.swing.GroupLayout(configPanel);
        configPanel.setLayout(configPanelLayout);
        configPanelLayout.setHorizontalGroup(
            configPanelLayout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(configPanelLayout.createSequentialGroup()
                .addContainerGap()
                .addComponent(cellsCheckBox)
                .addGap(18, 18, 18)
                .addComponent(candidatesCheckBox)
                .addGap(18, 18, 18)
                .addComponent(candLabel)
                .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.UNRELATED)
                .addComponent(candComboBox, javax.swing.GroupLayout.PREFERRED_SIZE, 58, javax.swing.GroupLayout.PREFERRED_SIZE)
                .addContainerGap(113, Short.MAX_VALUE))
        );
        configPanelLayout.setVerticalGroup(
            configPanelLayout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(configPanelLayout.createSequentialGroup()
                .addContainerGap()
                .addGroup(configPanelLayout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE)
                    .addComponent(cellsCheckBox)
                    .addComponent(candidatesCheckBox)
                    .addComponent(candLabel)
                    .addComponent(candComboBox, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE))
                .addContainerGap(javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE))
        );

        progressPanel.setBorder(javax.swing.BorderFactory.createTitledBorder(bundle.getString("BackdoorSearchDialog.progressPanel.title"))); // NOI18N

        searchLabel.setText(bundle.getString("BackdoorSearchDialog.searchLabel.text")); // NOI18N

        javax.swing.GroupLayout progressPanelLayout = new javax.swing.GroupLayout(progressPanel);
        progressPanel.setLayout(progressPanelLayout);
        progressPanelLayout.setHorizontalGroup(
            progressPanelLayout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(progressPanelLayout.createSequentialGroup()
                .addContainerGap()
                .addGroup(progressPanelLayout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
                    .addComponent(searchLabel)
                    .addComponent(searchProgressBar, javax.swing.GroupLayout.DEFAULT_SIZE, 512, Short.MAX_VALUE))
                .addContainerGap())
        );
        progressPanelLayout.setVerticalGroup(
            progressPanelLayout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(progressPanelLayout.createSequentialGroup()
                .addContainerGap()
                .addComponent(searchLabel)
                .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)
                .addComponent(searchProgressBar, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)
                .addContainerGap(javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE))
        );

        resultPanel.setBorder(javax.swing.BorderFactory.createTitledBorder(bundle.getString("BackdoorSearchDialog.resultPanel.title"))); // NOI18N

        singlesResultLabel.setText(bundle.getString("BackdoorSearchDialog.singlesResultLabel.text")); // NOI18N

        singlesResultList.setModel(new javax.swing.AbstractListModel() {
            String[] strings = { "Item 1", "Item 2", "Item 3", "Item 4", "Item 5" };
            public int getSize() { return strings.length; }
            public Object getElementAt(int i) { return strings[i]; }
        });
        jScrollPane1.setViewportView(singlesResultList);

        javax.swing.GroupLayout singlesResultPanelLayout = new javax.swing.GroupLayout(singlesResultPanel);
        singlesResultPanel.setLayout(singlesResultPanelLayout);
        singlesResultPanelLayout.setHorizontalGroup(
            singlesResultPanelLayout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(singlesResultPanelLayout.createSequentialGroup()
                .addComponent(singlesResultLabel)
                .addContainerGap(135, Short.MAX_VALUE))
            .addComponent(jScrollPane1, javax.swing.GroupLayout.DEFAULT_SIZE, 223, Short.MAX_VALUE)
        );
        singlesResultPanelLayout.setVerticalGroup(
            singlesResultPanelLayout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(singlesResultPanelLayout.createSequentialGroup()
                .addComponent(singlesResultLabel)
                .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)
                .addComponent(jScrollPane1, javax.swing.GroupLayout.DEFAULT_SIZE, 216, Short.MAX_VALUE))
        );

        progressResultLabel.setText(bundle.getString("BackdoorSearchDialog.progressResultLabel.text")); // NOI18N

        progressResultList.setModel(new javax.swing.AbstractListModel() {
            String[] strings = { "Item 1", "Item 2", "Item 3", "Item 4", "Item 5" };
            public int getSize() { return strings.length; }
            public Object getElementAt(int i) { return strings[i]; }
        });
        jScrollPane2.setViewportView(progressResultList);

        javax.swing.GroupLayout progressResultPanelLayout = new javax.swing.GroupLayout(progressResultPanel);
        progressResultPanel.setLayout(progressResultPanelLayout);
        progressResultPanelLayout.setHorizontalGroup(
            progressResultPanelLayout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(progressResultPanelLayout.createSequentialGroup()
                .addContainerGap()
                .addGroup(progressResultPanelLayout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
                    .addComponent(jScrollPane2, javax.swing.GroupLayout.DEFAULT_SIZE, 273, Short.MAX_VALUE)
                    .addGroup(progressResultPanelLayout.createSequentialGroup()
                        .addComponent(progressResultLabel)
                        .addContainerGap(132, Short.MAX_VALUE))))
        );
        progressResultPanelLayout.setVerticalGroup(
            progressResultPanelLayout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(progressResultPanelLayout.createSequentialGroup()
                .addComponent(progressResultLabel)
                .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)
                .addComponent(jScrollPane2, javax.swing.GroupLayout.DEFAULT_SIZE, 216, Short.MAX_VALUE))
        );

        javax.swing.GroupLayout resultPanelLayout = new javax.swing.GroupLayout(resultPanel);
        resultPanel.setLayout(resultPanelLayout);
        resultPanelLayout.setHorizontalGroup(
            resultPanelLayout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(resultPanelLayout.createSequentialGroup()
                .addContainerGap()
                .addComponent(singlesResultPanel, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE)
                .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)
                .addComponent(progressResultPanel, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE)
                .addContainerGap())
        );
        resultPanelLayout.setVerticalGroup(
            resultPanelLayout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(javax.swing.GroupLayout.Alignment.TRAILING, resultPanelLayout.createSequentialGroup()
                .addGroup(resultPanelLayout.createParallelGroup(javax.swing.GroupLayout.Alignment.TRAILING)
                    .addComponent(progressResultPanel, javax.swing.GroupLayout.Alignment.LEADING, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE)
                    .addComponent(singlesResultPanel, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE))
                .addContainerGap())
        );

        startButton.setMnemonic(ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.startButton.mnemonic").charAt(0));
        startButton.setText(bundle.getString("BackdoorSearchDialog.startButton.text")); // NOI18N
        startButton.addActionListener(new java.awt.event.ActionListener() {
            public void actionPerformed(java.awt.event.ActionEvent evt) {
                startButtonActionPerformed(evt);
            }
        });

        closeButton.setMnemonic(ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.stopButton.mnemonic").charAt(0));
        closeButton.setText(bundle.getString("BackdoorSearchDialog.closeButton.text")); // NOI18N
        closeButton.addActionListener(new java.awt.event.ActionListener() {
            public void actionPerformed(java.awt.event.ActionEvent evt) {
                closeButtonActionPerformed(evt);
            }
        });

        stopButton.setMnemonic(ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.closeButton.mnemonic").charAt(0));
        stopButton.setText(bundle.getString("BackdoorSearchDialog.stopButton.text")); // NOI18N
        stopButton.setEnabled(false);
        stopButton.addActionListener(new java.awt.event.ActionListener() {
            public void actionPerformed(java.awt.event.ActionEvent evt) {
                stopButtonActionPerformed(evt);
            }
        });

        javax.swing.GroupLayout layout = new javax.swing.GroupLayout(getContentPane());
        getContentPane().setLayout(layout);
        layout.setHorizontalGroup(
            layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(javax.swing.GroupLayout.Alignment.TRAILING, layout.createSequentialGroup()
                .addContainerGap()
                .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.TRAILING)
                    .addComponent(resultPanel, javax.swing.GroupLayout.Alignment.LEADING, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE)
                    .addComponent(progressPanel, javax.swing.GroupLayout.Alignment.LEADING, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE)
                    .addComponent(configPanel, javax.swing.GroupLayout.Alignment.LEADING, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE)
                    .addGroup(layout.createSequentialGroup()
                        .addComponent(startButton)
                        .addGap(6, 6, 6)
                        .addComponent(stopButton)
                        .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)
                        .addComponent(closeButton)))
                .addContainerGap())
        );

        layout.linkSize(javax.swing.SwingConstants.HORIZONTAL, new java.awt.Component[] {closeButton, startButton, stopButton});

        layout.setVerticalGroup(
            layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
            .addGroup(layout.createSequentialGroup()
                .addContainerGap()
                .addComponent(configPanel, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)
                .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)
                .addComponent(progressPanel, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)
                .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)
                .addComponent(resultPanel, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE)
                .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED, javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE)
                .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE)
                    .addComponent(startButton)
                    .addComponent(closeButton)
                    .addComponent(stopButton))
                .addContainerGap())
        );

        pack();
    }// </editor-fold>//GEN-END:initComponents

    private void cellsCheckBoxActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_cellsCheckBoxActionPerformed
        Options.getInstance().setBdsSearchForCells(cellsCheckBox.isSelected());
    }//GEN-LAST:event_cellsCheckBoxActionPerformed

    private void candidatesCheckBoxActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_candidatesCheckBoxActionPerformed
        Options.getInstance().setBdsSearchForCandidates(candidatesCheckBox.isSelected());
        candComboBox.setEnabled(candidatesCheckBox.isSelected());
    }//GEN-LAST:event_candidatesCheckBoxActionPerformed

    private void candComboBoxActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_candComboBoxActionPerformed
        Options.getInstance().setBdsSearchCandidatesAnz(candComboBox.getSelectedIndex());
    }//GEN-LAST:event_candComboBoxActionPerformed

    private void closeButtonActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_closeButtonActionPerformed
        setVisible(false);
    }//GEN-LAST:event_closeButtonActionPerformed

    private void startButtonActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_startButtonActionPerformed
        // reset everything
        singlesListModel.clear();
        singlesResultList.repaint();
        progressListModel.clear();
        progressResultList.repaint();
        // start the thread
        thread = new Thread(this);
        thread.start();
        setFinished(false);
        // change buttons
        adjustGUI();
    }//GEN-LAST:event_startButtonActionPerformed

    private void stopButtonActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_stopButtonActionPerformed
        if (thread != null && thread.isAlive()) {
            thread.interrupt();
            try {
                thread.join();
            } catch (InterruptedException ex) {
                Logger.getLogger(BackdoorSearchDialog.class.getName()).log(Level.SEVERE, null, ex);
            }
            update();
        }
    }//GEN-LAST:event_stopButtonActionPerformed

    /**
     * Override to check for a valid sudoku.
     * @param visible
     */
    @Override
    public void setVisible(boolean visible) {
        if (visible) {
            // check if a sudoku is set (more than 16 clues)
            int anz = sudokuPanel.getSudoku().getSolvedCellsAnz();
            if (anz <= 16) {
                JOptionPane.showMessageDialog(this, ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.error.message") + " (" + anz + ")",
                        ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.error.title"), JOptionPane.ERROR_MESSAGE);
                return;
            }
        }
        super.setVisible(visible);
    }

    /**
     * The search is done in a background thread: A maximum of 12 searches is conducted
     * (singles/progress, cells/candidates, up to combinations of three).<br>
     */
    @Override
    public void run() {
//        System.out.println("Thread started!");
        orgSudoku = sudokuPanel.getSudoku().clone();
        //solvedSudoku = sudokuPanel.getSolvedSudoku();
        sudoku = orgSudoku.clone();
        solver = sudokuPanel.getSolver();
        // makes sure the GUI is correctly displayed
        EventQueue.invokeLater(updateRunnable);
        try {
            // search for singles first
            if (Options.getInstance().isBdsSearchForCells()) {
                // we need the number of unsolved cells
                int anz = orgSudoku.getUnsolvedCellsAnz();
                //System.out.println("thread: search 1");
                // singles backdoor: singles only
                setAnzFound(0);
                if (!checkSingles(1, anz, null)) {
                    int maxAnz = SudokuUtil.combinations(anz, 2);
                    //System.out.println("thread: search 2");
                    if (!checkSingles(2, maxAnz, null)) {
                        //System.out.println("thread: search 3");
                        maxAnz = SudokuUtil.combinations(anz, 3);
                        checkSingles(3, maxAnz, null);
                        //System.out.println("Thread: done");
                    }
                }
                // singles backdoor: progress measure
                setAnzFound(0);
                if (!checkSingles(1, anz, Options.getInstance().solverStepsProgress)) {
                    int maxAnz = SudokuUtil.combinations(anz, 2);
                    //System.out.println("thread: search 2");
                    if (!checkSingles(2, maxAnz, Options.getInstance().solverStepsProgress)) {
                        //System.out.println("thread: search 3");
                        maxAnz = SudokuUtil.combinations(anz, 3);
                        checkSingles(3, maxAnz, Options.getInstance().solverStepsProgress);
                        //System.out.println("Thread: done");
                    }
                }
            }
            // now for candidates
            if (Options.getInstance().isBdsSearchForCandidates()) {
                // collect all candidates
                int anz = 0;
                //SudokuCell[] cells = orgSudoku.getCells();
                candidates.clear();
                for (int i = 0; i < Sudoku2.LENGTH; i++) {
                    if (sudoku.getValue(i) == 0) {
                        int[] cands = sudoku.getAllCandidates(i);
                        for (int j = 0; j < cands.length; j++) {
                            if (cands[j] != sudoku.getSolution(i)) {
                                candidates.add(new Candidate(i, cands[j]));
                                anz++;
                            }
                        }
                    }
                }
                // candidates backdoor: singles only
                setAnzFound(0);
                int maxDepth = Options.getInstance().getBdsSearchCandidatesAnz() + 1;
                if (!checkCandidates(1, anz, candidates, null) && maxDepth > 1) {
                    int maxAnz = SudokuUtil.combinations(anz, 2);
                    //System.out.println("thread: search 2 (" + maxAnz + ")");
                    if (!checkCandidates(2, maxAnz, candidates, null) && maxDepth > 2) {
                        maxAnz = SudokuUtil.combinations(anz, 3);
                        //System.out.println("thread: search 3 (" + maxAnz + ")");
                        checkCandidates(3, maxAnz, candidates, null);
                        //System.out.println("Thread: done");
                    }
                }
                // candidates backdoor: progress measure
                setAnzFound(0);
                if (!checkCandidates(1, anz, candidates, Options.getInstance().solverStepsProgress) && maxDepth > 1) {
                    int maxAnz = SudokuUtil.combinations(anz, 2);
                    //System.out.println("thread: search 2 (" + maxAnz + ")");
                    if (!checkCandidates(2, maxAnz, candidates, Options.getInstance().solverStepsProgress) && maxDepth > 2) {
                        maxAnz = SudokuUtil.combinations(anz, 3);
                        //System.out.println("thread: search 3 (" + maxAnz + ")");
                        checkCandidates(3, maxAnz, candidates, Options.getInstance().solverStepsProgress);
                        //System.out.println("Thread: done");
                    }
                }
            }
        } catch (InterruptedException ex) {
            // stop button pressed
            return;
        }
        // normal end
        setFinished(true);
        triggerUpdateProgressbar(ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.searchLabel.text"), 100, 100);
        EventQueue.invokeLater(updateRunnable);
        //System.out.println("Thread finished!");
    }

    /**
     * Adjusts the enabled state of all GUI items
     */
    private void adjustGUI() {
        if (thread != null && thread.isAlive() && !isFinished()) {
            startButton.setEnabled(false);
            stopButton.setEnabled(true);
            cellsCheckBox.setEnabled(false);
            candidatesCheckBox.setEnabled(false);
            candComboBox.setEnabled(false);
            closeButton.setEnabled(false);
//            System.out.println("adjust: running");
        } else {
            startButton.setEnabled(true);
            stopButton.setEnabled(false);
            cellsCheckBox.setEnabled(true);
            candidatesCheckBox.setEnabled(true);
            candComboBox.setEnabled(candidatesCheckBox.isSelected());
            closeButton.setEnabled(true);
//            System.out.println("adjust: stopped");
        }
    }

    /**
     * Reads all available items from the queues and adds them
     * to the lists.<br>
     * <b>CAUTION:</b> Must be called from within the swing thread (either
     * from an event handler or via {@link #updateRunnable}.
     */
    @SuppressWarnings("unchecked")
    private void update() {
        String str = null;
        // first singlesResultList
        boolean doRepaint = false;
        while ((str = singlesQueue.poll()) != null) {
            singlesListModel.addElement(str);
            doRepaint = true;
        }
        if (doRepaint) {
            singlesResultList.repaint();
        }
        // then progressResultList
        doRepaint = false;
        while ((str = progressQueue.poll()) != null) {
            progressListModel.addElement(str);
            doRepaint = true;
        }
        if (doRepaint) {
            progressResultList.repaint();
        }
        adjustGUI();
    }

    /**
     * Updates the progress bar
     */
    private void updateProgressBar() {
        searchLabel.setText(getProgressLabelString());
        searchProgressBar.setMaximum(getProgressBarMax());
        searchProgressBar.setValue(getProgressBarAct());
    }

    /**
     * Triggers an update of the progress bar from within the background thread.
     * The attributes have to be set via their getters and setters (they are
     * synchronized)
     * @param text
     * @param max
     * @param act
     */
    private void triggerUpdateProgressbar(String text, int max, int act) {
        setProgressLabelString(text);
        setProgressBarMax(max);
        setProgressBarAct(act);
        EventQueue.invokeLater(progressBarRunnable);
    }

    /**
     * Checks the sudoku for backdoors using combinations of candidates. <code>depth</code>
     * can be 1, 2 or 3 (number of candidates in each try).
     * @param depth
     * @param max
     * @param candidates
     * @param stepConfigs
     * @return
     */
    private boolean checkCandidates(int depth, int max, List<Candidate> candidates, StepConfig[] stepConfigs)
            throws InterruptedException {
        boolean found = false;
        int end = candidates.size();
        int counter = 0;
        String startStr = ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.search_candidates") + " (";
        if (stepConfigs == null) {
            startStr += ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.singles");
        } else {
            startStr += ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.progress");
        }
        startStr += " - ";
        String label = startStr + ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.search_candidates1");
        if (depth == 2) {
            label = startStr + ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.search_candidates2");
        } else if (depth == 3) {
            label = startStr + ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.search_candidates3");
        }
        label += ")";
        for (int i = 0; i < end; i++) {
            if (depth == 1) {
                if (checkSingleOrCandidate(-1, -1, -1, candidates.get(i), null, null, stepConfigs)) {
                    found = true;
                    incAnzFound();
                    if (getAnzFound() > MAX_FOUND) {
                        return true;
                    }
                }
                triggerUpdateProgressbar(label, max, ++counter);
            } else {
                for (int j = i + 1; j < end; j++) {
                    if (depth == 2) {
                        if (checkSingleOrCandidate(-1, -1, -1, candidates.get(i), candidates.get(j), null, stepConfigs)) {
                            found = true;
                            incAnzFound();
                            if (getAnzFound() > MAX_FOUND) {
                                return true;
                            }
                        }
                        triggerUpdateProgressbar(label, max, ++counter);
                    } else {
                        for (int k = j + 1; k < end; k++) {
                            if (checkSingleOrCandidate(-1, -1, -1, candidates.get(i), candidates.get(j), candidates.get(k), stepConfigs)) {
                                found = true;
                                incAnzFound();
                                if (getAnzFound() > MAX_FOUND) {
                                    return true;
                                }
                            }
                            triggerUpdateProgressbar(label, max, ++counter);
                        }
                    }
                }
            }
        }
        return found;
    }

    /**
     * Checks the sudoku for singles only backdoors. <code>depth</code>
     * can be 1, 2 or 3 (number of cells in each try).<br>
     * @param depth
     * @param max
     * @param stepConfigs
     * @return
     */
    private boolean checkSingles(int depth, int max, StepConfig[] stepConfigs)
            throws InterruptedException {
        boolean found = false;
        int end = orgSudoku.getCells().length;
        int counter = 0;
        String startStr = ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.search_cells") + " (";
        if (stepConfigs == null) {
            startStr += ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.singles");
        } else {
            startStr += ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.progress");
        }
        startStr += " - ";
        String label = startStr + ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.search_cells1");
        if (depth == 2) {
            label = startStr + ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.search_cells2");
        } else if (depth == 3) {
            label = startStr + ResourceBundle.getBundle("intl/BackdoorSearchDialog").getString("BackdoorSearchDialog.search_cells3");
        }
        label += ")";
        for (int i = 0; i < end; i++) {
            if (orgSudoku.getValue(i) != 0) {
                // cell already set
                continue;
            }
            if (depth == 1) {
                if (checkSingleOrCandidate(i, -1, -1, null, null, null, stepConfigs)) {
                    found = true;
                    incAnzFound();
                    if (getAnzFound() > MAX_FOUND) {
                        return true;
                    }
                }
                triggerUpdateProgressbar(label, max, ++counter);
            } else {
                for (int j = i + 1; j < end; j++) {
                    if (orgSudoku.getValue(j) != 0) {
                        // cell already set
                        continue;
                    }
                    if (depth == 2) {
                        if (checkSingleOrCandidate(i, j, -1, null, null, null, stepConfigs)) {
                            found = true;
                            incAnzFound();
                            if (getAnzFound() > MAX_FOUND) {
                                return true;
                            }
                        }
                        triggerUpdateProgressbar(label, max, ++counter);
                    } else {
                        for (int k = j + 1; k < end; k++) {
                            if (orgSudoku.getValue(k) != 0) {
                                // cell already set
                                continue;
                            }
                            if (checkSingleOrCandidate(i, j, k, null, null, null, stepConfigs)) {
                                found = true;
                                incAnzFound();
                                if (getAnzFound() > MAX_FOUND) {
                                    return true;
                                }
                            }
                            triggerUpdateProgressbar(label, max, ++counter);
                        }
                    }
                }
            }
        }
        return found;
    }

    /**
     * Checks if the sudoku can be solved with singles only or with the
     * techniques defined in {@link Options#solverStepsProgress}, after the
     * cells <code>index1</code>, <code>index2</code> and <code>index3</code>
     * have been set. If <code>index2</code> and/or <code>index3</code> are <code>-1</code>,
     * they are ignored.<br>
     * If <code>candx</code> is not <code>null</code>, a search for a candidate combination is
     * done (same rules as above).
     * @param index1
     * @param index2
     * @param index3
     * @param cand1
     * @param cand2
     * @param cand3
     * @param stepConfigs
     * @return
     */
    private boolean checkSingleOrCandidate(int index1, int index2, int index3, Candidate cand1,
            Candidate cand2, Candidate cand3, StepConfig[] stepConfigs)
            throws InterruptedException {
        if (thread.isInterrupted()) {
            throw new InterruptedException();
        }
        // set the original sudoku
        sudoku.set(orgSudoku);
        if (cand1 == null) {
            // set the cells to the correct values
//            System.out.println("index1: " + sudoku.getSolution(index1) + "/" + sudoku.getValue(index1));
            sudoku.setCell(index1, sudoku.getSolution(index1));
//            System.out.println("sudoku: " + sudoku.getSudoku(ClipboardMode.VALUES_ONLY));
//            if (index2 >= 0) {
////                sudoku.setCell(index2, sudoku.getValue(index2));
//                System.out.println("index2: " + sudoku.getSolution(index2) + "/" + sudoku.getValue(index2));
//                sudoku.setCell(index2, sudoku.getSolution(index2));
//            }
//            if (index3 >= 0) {
////                sudoku.setCell(index3, sudoku.getValue(index3));
//                System.out.println("index3: " + sudoku.getSolution(index3) + "/" + sudoku.getValue(index3));
//                sudoku.setCell(index3, sudoku.getSolution(index3));
//            }
        } else {
            // remove the candidates
            sudoku.setCandidate(cand1.getIndex(), cand1.getValue(), false);
            if (cand2 != null) {
                sudoku.setCandidate(cand2.getIndex(), cand2.getValue(), false);
            }
            if (cand3 != null) {
                sudoku.setCandidate(cand3.getIndex(), cand3.getValue(), false);
            }
        }
        // now try and solve
        boolean isSolved = false;
        if (stepConfigs == null) {
            isSolved = solver.solveSinglesOnly(sudoku);
        } else {
            isSolved = solver.solveWithSteps(sudoku, stepConfigs);
        }
        if (isSolved) {
            String cellString = "";
            if (cand1 == null) {
                cellString = SolutionStep.getCellPrint(index1, false);
                if (index2 >= 0) {
                    cellString += ", " + SolutionStep.getCellPrint(index2, false);
                }
                if (index3 >= 0) {
                    cellString += ", " + SolutionStep.getCellPrint(index3, false);
                }
            } else {
                cellString = SolutionStep.getCellPrint(cand1.getIndex(), false) + "<>" + cand1.getValue();
                if (cand2 != null) {
                    cellString += ", " + SolutionStep.getCellPrint(cand2.getIndex(), false) + "<>" + cand2.getValue();
                }
                if (cand3 != null) {
                    cellString += ", " + SolutionStep.getCellPrint(cand2.getIndex(), false) + "<>" + cand3.getValue();
                }
            }
            if (stepConfigs == null) {
                singlesQueue.offer(cellString);
            } else {
                progressQueue.offer(cellString);
            }
            EventQueue.invokeLater(updateRunnable);
            return true;
        }
        return false;
    }

    /**
     * @return the finished
     */
    private synchronized boolean isFinished() {
        return finished;
    }

    /**
     * @return the progressLabelString
     */
    private synchronized String getProgressLabelString() {
        return progressLabelString;
    }

    /**
     * @param progressLabelString the progressLabelString to set
     */
    private synchronized void setProgressLabelString(String progressLabelString) {
        this.progressLabelString = progressLabelString;
    }

    /**
     * @return the progressBarMax
     */
    private synchronized int getProgressBarMax() {
        return progressBarMax;
    }

    /**
     * @param progressBarMax the progressBarMax to set
     */
    private synchronized void setProgressBarMax(int progressBarMax) {
        this.progressBarMax = progressBarMax;
    }

    /**
     * @return the progressBarAct
     */
    private synchronized int getProgressBarAct() {
        return progressBarAct;
    }

    /**
     * @param progressBarAct the progressBarAct to set
     */
    private synchronized void setProgressBarAct(int progressBarAct) {
        this.progressBarAct = progressBarAct;
    }

    /**
     * @param finished the finished to set
     */
    private synchronized void setFinished(boolean finished) {
        this.finished = finished;
    }

    /**
     * @return the anzFound
     */
    private synchronized int getAnzFound() {
        return anzFound;
    }

    /**
     * @param anzFound the anzFound to set
     */
    private synchronized void setAnzFound(int anzFound) {
        this.anzFound = anzFound;
    }

    /**
     * Increment anzFound
     */
    private synchronized void incAnzFound() {
        anzFound++;
    }

    /**
     * @param args the command line arguments
     */
    public static void main(
            String args[]) {
        EventQueue.invokeLater(new Runnable() {

            @Override
            public void run() {
                BackdoorSearchDialog dialog = new BackdoorSearchDialog(new javax.swing.JFrame(), true, null);
                dialog.addWindowListener(new java.awt.event.WindowAdapter() {

                    @Override
                    public void windowClosing(java.awt.event.WindowEvent e) {
                        System.exit(0);
                    }
                });
                dialog.setVisible(true);
            }
        });
    }
    // Variables declaration - do not modify//GEN-BEGIN:variables
    private javax.swing.JComboBox candComboBox;
    private javax.swing.JLabel candLabel;
    private javax.swing.JCheckBox candidatesCheckBox;
    private javax.swing.JCheckBox cellsCheckBox;
    private javax.swing.JButton closeButton;
    private javax.swing.JPanel configPanel;
    private javax.swing.JScrollPane jScrollPane1;
    private javax.swing.JScrollPane jScrollPane2;
    private javax.swing.JPanel progressPanel;
    private javax.swing.JLabel progressResultLabel;
    private javax.swing.JList progressResultList;
    private javax.swing.JPanel progressResultPanel;
    private javax.swing.JPanel resultPanel;
    private javax.swing.JLabel searchLabel;
    private javax.swing.JProgressBar searchProgressBar;
    private javax.swing.JLabel singlesResultLabel;
    private javax.swing.JList singlesResultList;
    private javax.swing.JPanel singlesResultPanel;
    private javax.swing.JButton startButton;
    private javax.swing.JButton stopButton;
    // End of variables declaration//GEN-END:variables
}
